import java.util.HashMap;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-20
 * Time: 10:25
 */
class ListNode{
    int val;
    ListNode next;

    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public class Day3 {
    //234.回文链表 - 标记
    public boolean isPalindrome1(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            stack.push(slow.val);
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null && fast.next == null){
            slow = slow.next;
        }
        while (slow != null){
            if (!stack.empty() && slow.val == stack.peek()){
                stack.pop();
            }else{
                break;
            }
            slow = slow.next;
        }
        return stack.empty();
    }
    public boolean isPalindrome2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode node = head;
        while (node != null){
            stack.push(node.val);
            node = node.next;
        }
        node = head;
        while (node != null){
            if (!stack.empty() && node.val != stack.pop()){
                return false;
            }
            node = node.next;
        }
        return stack.empty();
    }
    public boolean isPalindrome3(ListNode head) {
        if (head == null){
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            cur = cur.next;
            slow.next = tmp;
            tmp = slow;
            slow = cur;
        }
        if (fast != null && fast.next == null){
            slow = slow.next;
        }
        while (slow != null){
            if (slow.val != tmp.val){
                return false;
            }
            slow = slow.next;
            tmp = tmp.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        int s1 = 0,s2 = 0,t = 1;

        while(head != null) {
            s1 = s1*10 + head.val;
            s2 = s2 + t*head.val;
            t = t*10;
            head = head.next;
        }
        return s1 == s2;
    }

    //496.下一个更大元素I - HashMap - 标记
    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums1.length; i++) {
            int j = 0;
            for (j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]){
                    stack.push(nums1[i]);
                }else if (!stack.empty() && nums2[j] > stack.peek()){
                    stack.pop();
                    ret[i] = nums2[j];
                    break;
                }
            }
            if (j == nums2.length){
                ret[i] = -1;
                if (!stack.empty()){
                    stack.pop();
                }
            }
        }
        return ret;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<Integer>();
        HashMap<Integer, Integer> hasMap = new HashMap<Integer, Integer>();

        int[] result = new int[nums1.length];

        for(int num : nums2) {
            while(!stack.isEmpty() && stack.peek()<num){
                hasMap.put(stack.pop(), num);
            }
            stack.push(num);
        }

        for(int i = 0; i < nums1.length; i++) result[i] = hasMap.getOrDefault(nums1[i], -1);

        return result;
    }

    //682.棒球比赛 - 标记
    public int calPoints1(String[] operations) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < operations.length; i++) {
            String str = operations[i];
            switch (str){
                case "+":
                    int num1 = stack.pop();
                    int num2 = stack.peek();
                    stack.push(num1);
                    stack.push(num1 + num2);
                    break;
                case "D":
                    int num = stack.peek() * 2;
                    stack.push(num);
                    break;
                case "C":
                    stack.pop();
                    break;
                default:
                    stack.push(Integer.parseInt(str));
                    break;
            }
        }
        int ret = 0;
        while (!stack.empty()){
            ret += stack.pop();
        }
        return ret;
    }

    public int calPoints(String[] ops) {
        int[] arr = new int[ops.length];
        int i=0;
        for(String s:ops){
            switch (s){
                case "+":arr[i]=arr[i-1]+arr[i-2];i++;break;
                case "D":arr[i]=2*arr[i-1];i++;break;
                case "C":arr[i-1]=0;i--;break;
                default:
                    arr[i]=Integer.valueOf(s);
                    i++;
            }
        }
        int sum=0;
        for (int j = 0; j <arr.length ; j++) {
            sum+=arr[j];
        }
        return sum;
    }

    //844.比较含退格的字符串 - 标记
    public boolean backspaceCompare1(String s, String t) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#'){
                if (!stack1.empty()) {
                    stack1.pop();
                }
            }else{
                stack1.push(c);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (c == '#'){
                if (!stack2.empty()) {
                    stack2.pop();
                }
            }else{
                stack2.push(c);
            }
        }
        while (!stack1.empty() && !stack2.empty()){
            if (stack1.peek() == stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else{
                break;
            }
        }
        return stack1.empty() && stack2.empty();
    }

    public boolean backspaceCompare2(String s, String t) {
        return getString(s).equals(getString(t));
    }
    public String getString(String s){
        char[] ret = s.toCharArray();
        int n = ret.length;

        int slow = 0;
        for (int fast = 0; fast < n; fast++) {
            if (ret[fast] == '#'){
                if (slow > 0){
                    slow--;
                }
            }else{
                ret[slow++] = ret[fast];
            }
        }
        return new String(ret,0,slow);
    }


}
